package com.study.algorithm.sort;

import java.text.MessageFormat;
import java.util.Arrays;

/**
 * 希尔排序。
 *
 * <p>希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
 *
 * <p>学习插入排序的时候，我们会发现一个很不友好的事儿，如果已排序的分组元素为 {2,5,7,9,10}，未排序的分组
 * 元素为 {1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真正的插入，
 * 每次交换只能和相邻的元素交换位置。那如果我们要提高效率，直观的想法就是一次交换，能把1放到更前面的位置，比如一次交换就能把1插到2和5之间，
 * 这样一次交换1就向前走了5个位置，可以减少交换的次数。
 *
 * <p><B>排序原理：</B>
 * <ol>
 *   <li>选定一个增长量 h ，按照增长量 h 作为数据分组的一句，对数据进行分组。</li>
 *   <li>对分好组的每一组数据完成插入排序。</li>
 *   <li>减少增长量，最小减为 1，重复第二步操作。</li>
 * </ol>
 *
 * @author chenganbang
 */
public class Shell implements Sort {

  private Shell() {
  }

  private static class Holder {
    private static final Shell INSTANCE = new Shell();
  }

  public static Shell getInstance() {
    return Shell.Holder.INSTANCE;
  }

  /**
   * 对数组 source 进行排序。
   *
   * <p>假设待排序数组：[9, 1, 2, 5, 7, 4, 8, 6, 3]，那么排序过程如下：
   * <ul>
   * <li>第 1 趟排序结果：[4, 1, 2, 3, 7, 9, 8, 6, 5]
   * <li>第 2 趟排序结果：[2, 1, 4, 3, 7, 6, 5, 9, 8]
   * <li>第 3 趟排序结果：[1, 2, 3, 4, 6, 5, 7, 8, 9]
   * </ul>
   * 排好序结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]
   *
   * @param source
   *     数组 source
   */
  @Override
  public void sort(Comparable[] source) {
    int h = getInitialStepSize(source.length);
    SortHelper sortHelper = SortHelper.getInstance();
    System.out.println("待排序数组：" + Arrays.toString(source));
    int j = 1;
    while (h >= 1) {
      for (int i = 0; i < source.length; i++) {
        if (i + h >= source.length) {
          continue;
        }
        if (sortHelper.greater(source[i], source[i + h])) {
          sortHelper.exchange(source, i, i + h);
        }
      }

      int index = j++;
      System.out.println(MessageFormat.format("第 {0} 趟增量：{1}", index, h));
      sortHelper.printArray(index, source);

      h = h / 2;
    }
    System.out.println("排好序结果：" + Arrays.toString(source));
  }

  private static int getInitialStepSize(int arrayLength) {
    int stepSize = arrayLength / 2 + 1;
    if (arrayLength % 2 == 0) {
      stepSize = arrayLength / 2;
    }
    return stepSize;
  }
}